class Solution 
{
    unordered_map<char, unordered_set<char>> edges; // 邻接表来存图
    unordered_map<char, int> in;    // 统计入度
    bool cheak; // 处理边界情况

public:
    string alienOrder(vector<string>& words) 
    {
        // 1. 建图 + 初始化入度哈希表
        for(auto& s : words)
        {
            for(auto& ch : s)
            {
                in[ch] = 0;
            }
        }

        int n = words.size();
        for(int i = 0; i < n; i++)
        {
            for(int j = i + 1; j < n; j++)
            {
                add(words[i], words[j]);
                if(cheak) return "";
            }
        }

        // 2. 拓扑排序
        queue<char> q;
        for(auto& [a, b] : in)
        {
            if(b == 0) q.push(a);
        }

        string ret;
        while(q.size())
        {
            char t = q.front(); q.pop();
            ret += t;
            for(char ch : edges[t])
            {
                if(--in[ch] == 0) q.push(ch);
            }
        }

        // 3. 判断是否有环
        for(auto& [a, b] : in)
            if(b != 0) return "";

        return ret;
    }

    void add(string& s1, string& s2)
    {
        int n = min(s1.size(), s2.size());
        int i = 0;
        for( ; i < n; i++)
        {
            if(s1[i] != s2[i])
            {
                char a = s1[i], b = s2[i];  // a -> b
                if(!edges.count(a) || !edges[a].count(b))
                {
                    edges[a].insert(b);
                    in[b]++;
                }
                break;
            }
        }

        if(i == s2.size() && i < s1.size())
            cheak = true;
    }
};